package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 17:16
 * @Description: BackpackVI$LintCode-564
 * <p>
 * <p>
 * 给定n个整数，分别是正整数A0,A1,A2,...,An-1
 * 一个正整数Target
 * 有多少种组合加起来是Target
 * 每个Ai能用多次次
 * <p>
 * eg:
 * 输入：A=[1,2,4],Target=4
 * 输出：6(1+1+1+1=4,2+2=4,1+1+2=4,1+2+1=4,2+1+1=4,4=4)
 * <p>
 * 不同于BackpackV,组合中数字可以按照不同的顺序，比如1+1+2和1+2+1算两种组合
 * 不能先处理第一个物品，再处理第二个物品，
 * 似乎更难，其实更简单，类似组合硬币问题
 * <p>
 * 关注最后一步：最后一个物品的重量是多少？
 * 关键点1：任何一个正确组合中，所有的物品总重量都是Target
 * 关键点2：如果最后一个物品重量是K,则前面的物品重量是Target-K
 * 最后求多少种情况，即把他们相加即可
 * <p>
 * step 1: 确定状态
 * 如果最后一个物品重量是A0,则要求有多少种组合能够拼成Target - A0
 * 如果最后一个物品重量是A1,则要求有多少种组合能够拼成Target - A1
 * ...
 * 如果最后一个物品重量是A(n-1),则要求有多少种组合能够拼成Target - A(n-1)
 * <p>
 * 组合数相加即可，同时满足顺序和无论有多少个
 * <p>
 * 子问题：
 * 原问题要求有多少种组合能拼成Target
 * <p>
 * 设f[i] = 有多少种组合能够拼出重量i
 * step 2: 转移方程
 * 设f[i] = 有多少种组合能够拼出重量i
 * f[i] = f[i-A0]+f[i-A1]+...+f[i-A(N-1)]
 * 多少种组合能拼出i  多少种组合能拼出i-A0     多少种组合能拼出i-A(N-1)
 * <p>
 * step 3:初始条件和边界值
 * 初始条件：
 * f[0]=1,有一种组合能拼出重量0（啥都不选）
 * 如果i<Aj,则对应的f[i-Aj]不加入f[i]
 * A0=1,A1=2,A2=4
 * f[3=f[3-A0]+f[3-A1]
 * step 4:计算顺序
 * f[i] = f[i-A0]+f[i-A1]+...+f[i-A(N-1)]
 * f[0]=1
 * 计算f[1],f[2],...,f[Target]
 * <p>
 * 结果f[Target]
 * <p>
 * 扩展：方式数>=1,求出其中一种方式，最后一个数可以是Pai[i]
 * Target Pai[Target] Pai[Target-Pai[Target]]
 * <p>
 * 求Pai[i]，f[i]>0===>f[i-Aj]>0,Pai[i]=j
 */
public class BackpackVi {



	public int backPackVi(int[] nums, int T) {
		int[] f = new int[T + 1];
		f[0] = 1;
		int i, j;
		for (i = 1; i <= T; i++) {
			f[i] = 0;
			for (j = 0; j < nums.length; j++) {
				if (i >= nums[j]) {
					f[i] += f[i - nums[j]];
				}
			}
		}
		return f[T];
	}


	public int backPackVi2(int[] nums, int T) {

		int[] f = new int[T+1];
		// pai[i]：如果能够拼出i,最后一个数字是多少
		//pai[i] if f[i]>=1,最后一个数字可以是pai[i]

		int[] pai = new int[T + 1];
		f[0] = 1;
		int i, j;
		for (i = 1; i <= T; i++) {
			f[i] = 0;
			for (j = 0; j < nums.length; j++) {
				if (i >= nums[j]) {
					f[i] += f[i - nums[j]];
					// 前面有一种方法可以拼出它
					if(f[i-nums[j]]>0){
						// 有一种方法可以使最后一个数字为num[j]
						pai[i] = nums[j];
					}
				}
			}
		}

		if(f[T]>0) {
			i = T;
			System.out.print(i + "=");
			while (i != 0) {
				System.out.print(pai[i]+" ");
				// sum now is i
				// last num can be pai[i]
				// previous sum is i-pai[i]
				i-=pai[i];
			}
			System.out.println();
		}
		return f[T];
	}

	public static void main(String[] args) {
		int[] nums = {1,2,4};
		int n = 4;
		BackpackVi instance = new BackpackVi();
		System.out.println(instance.backPackVi(nums,n));
		int[] nums2 = {5,7,13,17};
		int m = 32;
		System.out.println(instance.backPackVi2(nums2,m));

	}
}
